package com.cango.student.algorithm.lru;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class LRUCache {
    private int cacheSize = 10;
    private HashMap<String, Node> map = new HashMap<>();
    private Node head;
    private Node tail;

    public void LRUCache(int cacheSize) {
        this.cacheSize = cacheSize;
    }

    /**
     * 添加缓存
     * 先判断是否已有该缓存，如果有则直接放到链尾取出，
     * 如果没有，则判断是否已满，如果满了，删除链头数据，否则直接插到链尾
     */
    public void addCache(String key, String value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            if (node.next != null) {
                if (node.pre == null) {
                    head = node.next;
                } else {
                    node.pre.next = node.next;
                    node.next.pre = node.pre;
                }
                tail.next = node;
                node.pre = tail;
                node.next = null;
                tail = node;
            }
        } else {
            Node node = new Node(key, value);
            if (map.size() == cacheSize) {
                Node temp = head;
                head = head.next;
                map.remove(temp.key);
                node.pre = tail;
                tail.next = node;
                tail = node;
            } else {
                if (head == null) {
                    head = node;
                    tail = node;
                } else {
                    node.pre = tail;
                    tail.next = node;
                    tail = node;
                }
            }
            map.put(key, node);
        }
    }

    /**
     * 获取缓存
     * 先判断是否有缓存，如果有，需要把该缓存移动到链尾返回
     */
    public String getCache(String key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            if (node.next == null) {
                return node.value;
            }
            if (node.pre == null) {
                head = node.next;
            } else {
                node.pre.next = node.next;
                node.next.pre = node.pre;
            }
            tail.next = node;
            node.pre = tail;
            node.next = null;
            tail = node;
            return node.value;
        } else {
            return null;
        }
    }

    public void test() {
        Iterator<Map.Entry<String, Node>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<String, Node> entry = iterator.next();
            System.out.println(entry.getKey() + "--" + entry.getValue().value);
        }
    }

    public void test2() {
        Node temp = head;
        while (temp != null) {
            System.out.println(temp.key);
            temp = temp.next;
        }
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache();
        cache.addCache("key0", "value0");
        cache.addCache("key1", "value1");
        cache.addCache("key2", "value2");
        cache.addCache("key3", "value3");
        cache.addCache("key4", "value4");
        cache.addCache("key5", "value5");
        cache.addCache("key6", "value6");
        cache.addCache("key7", "value7");
        cache.addCache("key8", "value8");
        cache.addCache("key9", "value9");
        cache.getCache("key9");
        cache.test2();
    }

    class Node {
        String key;
        String value;
        Node pre;
        Node next;

        public Node(String key, String value) {
            this.key = key;
            this.value = value;
        }
    }
}
